package com.zdp.leetcodeMiddle;

import com.zdp.util.Heap;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
* 题目描述：
* 在未排序的数组中找到第 k 个最大的元素。
* 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 数组中第k个最大元素_215 {
    public static void main(String[] args) {
        数组中第k个最大元素_215 demo = new 数组中第k个最大元素_215();
        int[] nums = new int[] {
                3,2,1,5,6,4
        };
        Heap heap = new Heap();
        List<Integer> integers = heap.HeapSort(nums);
        System.out.println(integers.toString());
//        int kthLargest = demo.findKthLargest1(nums, 2);
//        System.out.println(kthLargest);
    }

    /*
    * 双层循环，暴力解，在数组中寻找k次
    * 每次都是找到当前数组最大的那个元素，然后将其记录
    * 下次寻找将跳过这个元素
    * */
    public int findKthLargest(int[] nums, int k) {

        Set<Integer> set = new HashSet<>();
        int max = Integer.MIN_VALUE;
        int index = -1;
        for(int i=0;i<k;i++){
            max = Integer.MIN_VALUE;
            index = -1;
            for(int j=0;j<nums.length;j++){
                if(set.contains(j)){
                    continue;
                }
                if(nums[j]>max){
                    index = j;
                    max = nums[j];
                }
            }
            set.add(index);
        }
        return max;
    }

    /*
    * 使用快排思想
    * */
    public int findKthLargest1(int[] nums,int k){

        return quickSort(nums,0,nums.length-1,nums.length-k);
    }
    public int quickSort(int[] nums,int left,int right,int k){
        int partition = getPartition(nums,left,right);
        if(partition == k){
            // 得到的枢轴正好是第k大的元素
            return nums[partition];
        }
        // 如果没有，就进行判断
        return partition < k? quickSort(nums,partition+1,right,k)
                :quickSort(nums,left,partition-1,k);
    }

    public int getPartition(int[] nums,int left,int right){
        // 设置一个基准值
        int partition = left + ((right-left)>>1);
        swap(nums,partition,right);
        // 基准值为 right
        int x = nums[right];
        // i 指向大于基准值的那个元素的前一位
        int i = left-1;
        for(int j=left;j<right;j++){
            if(nums[j]<=x){
                // 如果找到小于基准值的那个元素，就将其与大于基准值的那个数交换
                swap(nums,++i,j);
            }
        }
        swap(nums,i+1,right);
        return i+1;
    }

    public void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    /*
    * 解法三，利用堆排序
    * */
    public int findKthLargest2(int[] nums,int k){
        Heap demo = new Heap();
        List<Integer> integers = demo.HeapSort(nums);
        return integers.get(k-1);
    }
}
